package leetcode.code047;

import java.util.ArrayList;
import java.util.List;

public class Solution extends Solution047 {

	@Override
	public List<List<Integer>> permuteUnique(int[] nums) {
		List<Integer> able = new ArrayList<>();
		for (int i = 0; i < nums.length; i++) {
			able.add(i);
		}
		List<List<Integer>> ans = new ArrayList<>();
		List<Integer> temp = new ArrayList<>();
		this.permuteUnique(nums, able, temp, ans);
		return ans;
	}

	public void permuteUnique(int[] nums, List<Integer> able, List<Integer> temp, List<List<Integer>> ans) {
		if (able.size() == 0) {
			ans.add(new ArrayList<>(temp));//
			return;
		}
		List<Integer> cache = new ArrayList<>();// 1为了处理重复
		for (int i = 0; i < able.size(); i++) {
			Integer index = able.get(i);
			if (cache.contains(nums[index])) {// 2为了处理重复
				continue;
			}
			cache.add(nums[index]);// 3为了处理重复
			temp.add(nums[index]);
			able.remove(index);
			this.permuteUnique(nums, able, temp, ans);
			temp.remove(temp.size() - 1);
			able.add(i, index);
		}
	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
	}

}
